\pagestyle{empty}
\cleardoublepage
%\pagestyle{fancy}
\chapter{Exemplos e resultados}\label{cap5}

Neste capítulo são apresentados os resultados obtidos pela técnica proposta neste trabalho. É também mostrada a diferença nos resultados que as estruturas de dados utilizadas no particionamento fazem, comparando a \textit{quadtree} com a BSP. Os resultados para a técnica descrita neste trabalho são nomeados, como \textit{a priori} e comparados com os resultados para os mesmos modelos no trabalho de \cite{bib:MFreitas13} que são nomeados de \textit{a posteriori}, pois essa técnica segue uma 
abordagem de particionamento diferente.

O mesmo critério de particionamento, que é baseado na carga média, foi adotado para os exemplos que utilizaram a \textit{quadtree} como estrutura de particionamento. O algoritmo de geração de malha utilizado foi o mesmo em todos os testes para uma comparação justa entre os resultados.

A técnica descrita neste trabalho foi implementada em C++, utilizando a biblioteca de paralelismo em memória compartilhada OpenMP (\textit{Open Multi-Processing}) e a biblioteca de passagem de mensagens MPI (\textit{Message Passing Interface}) para paralelismo de memória distribuída. As versões com interface foram ainda implementadas com a biblioteca de renderização OpenGL (com suas bibliotecas glu, glut e glew), e a biblioteca de interfaces wxWidgets.

O computador utilizado para rodar os testes da implementação foi o cluster do CENAPAD-UFC com 48 nós, cada um com dois processadores Intel Westmere 6 cores X5650 EP e 24 GB de RAM, totalizando 576 núcleos de processamento e 1152GB de RAM. Os testes foram feitos utilizando 8 nós com memória distribuída e o gerador de malha apresentado na seção \ref{sec:Parallel_mesh_generation_Mesh_generation_by_a_slave_process}.

\section{Modelos}

Ao todo, foram executados 3 modelos de diferentes geometrias, alguns dos quais com buracos, para avaliar o comportamento da técnica em diferentes entradas. A Figura~\ref{fig:exemplos} mostra as fronteiras utilizadas pelo procedimento de geração em paralelo de malhas. 

 \begin{figure}[h]
     \begin{center}
     \includegraphics[width=0.8\textwidth]{fig/exemplos.png}
     \caption{Modelos utilizados para testes: Cilindro, Chave e Placa.} 
     \label{fig:exemplos}
     \end{center}
 \end{figure}


\section{Tamanho das Malhas} 

A Figura~\ref{fig:quantidade_elementos} mostra os tamanhos das malhas geradas sequencialmente, onde todos os resultados usam os mesmos modelos para a validação das ideias propostas neste trabalho. Como pode ser visto, os tamanhos das malhas variam aproximadamente de 1,2 milhões a 1,8 milhões de elementos. Os tamanhos das malhas e a quantidade de processadores utilizados são razoáveis para os teste aqui realizados, ilustrando bem o comportamento da técnica nestes modelos.

\begin{figure}[h]
      \begin{center}
      \includegraphics[width=0.6\textwidth]{fig/imagens_resultados/tamanhos.png}
      \caption{Quantidade de elementos gerados nos exemplos.} 
      \label{fig:quantidade_elementos}
      \end{center}
  \end{figure}

 \begin{figure}[h]
     \begin{center}
     \includegraphics[width=0.85\textwidth]{fig/key_mesh_highlight.png}
     \caption{Região entre submalhas.} 
     \label{fig:key_mesh_highlight}
     \end{center}
 \end{figure}  
  
 A Figura~\ref{fig:key_mesh_highlight} destaca uma região entre dois subdomínios do modelo Chave, com o objetivo de mostrar como as malhas geradas em paralelo se adequam perfeitamente (cada cor indica um processo diferente). Como pode ser visto, as funções de tamanho e forma nos triângulos gerados foram respeitadas, mesmo que eles tenham sido gerados por diferentes processos em diferentes subdomínios, ou mesmo pelo processo mestre, no passo de finalização da malha (elementos em preto).


 

\section{Qualidade}  

Para avaliar a qualidade das malhas geradas é utilizada uma métrica que usa $\alpha = {2R_i}/{R_c}$, onde $R_i$ e $R_c$ são os raios dos círculos inscrito e circunscrito a um dado triângulo da malha, respectivamente. Esta métrica $\alpha$ tem valor 1,0 para um triângulo equilátero. Quanto pior for a qualidade de um elemento, mais próximo de 0,0 é o valor de $\alpha$. Um elemento com $\alpha \leq$ 0,1 é dito ter uma qualidade muito pobre, enquanto que elementos com $\alpha \geq$ 0,7 têm boa qualidade.

A qualidade da malha de cada um dos três modelos é mostrada, respectivamente, nas figuras \ref{fig:qualidades_cilindro}, \ref{fig:qualidades_chave} e \ref{fig:qualidades_plate3}. Nessas figuras, os elementos gerados recebem uma classificação entre 0,1 e 1,0. Pode-se ver que existe um grande espaço vazio no início dos gráficos e logo após uma grande quantidade de elementos de boa qualidade, com $\alpha \geq$ 0,7. É visível que praticamente todos os elementos gerados se encontram numa estreita faixa próxima ao valor 1,0 (máxima qualidade) e que a quantidade de elementos nessa faixa é praticamente a mesma das malhas malhas geradas de forma sequencial. No geral, esse gráfico mostra que, para as três abordagens(\textit{a priori} com particionamento por BSP, \textit{a priori} com particionamento por \textit{quadtree} e \textit{a posteriori} com particionamento por \textit{quadtree}) a malha resultante é bastante boa.

As Figuras \ref{fig:quadtree_comp_dif_qualidade} e \ref{fig:bsp_dif_qualidades}  mostram a diferença em porcentual da qualidade da malha gerada sequencialmente com a gerada em paralelo. Para a técnica \textit{a priori} houve um crescimento na qualidade dos elementos gerados em paralelo na faixa de 0,6 a 0,9 e um decaimento na faixa próxima do valor 1,0. Ou seja, alguns elementos classificados como 1,0 reduziram sua qualidade e foram para uma outra faixa de valor um pouco mais abaixo, mas, mesmo assim, continuam com uma boa qualidade. Como visto na figura, a variação de qualidade para melhor ou pior não passa de 1,2$\%$ para a abordagem \textit{a priori} com \textit{quadtree}, 0,7$\%$ para a abordagem \textit{a priori} com BSP e de 0,06$\%$ para para a abordagem \textit{a posteriori} com \textit{quadtree}. A explicação disso é que em técnicas de particionamento \textit{a priori} são inseridos elementos que cortam a borda para gerar novos subdomínios, e esses cortes podem ficar em regiões geometricamente ruins,
 podendo influenciar diretamente nos elementos que 
serão gerados. Já nas técnicas de decomposição \textit{a posteriori} não é gerado nenhuma nova fronteira na criação dos subdomínios, fazendo assim a nova malha ser bem mais parecida com a sequencial. Isso, entretanto, não é um problema sério pois a qualidade da malha não varia muito como foi mostrado e esse aspecto ocorre, em geral, em regiões internas do modelo, onde isso não é crucial na maioria dos casos.  




    \begin{figure}[!ht]
    \centering
    \subfloat[Qualidade para a técnica \textit{a priori} com particionamento por BSP para o Cilindro.]
    {\label{fig:qualidade_cilindro}
     \begin{minipage}[c]{0.7\textwidth}{\includegraphics[width=\textwidth]{fig/imagens_resultados/qualidade_cilindro.png}}\end{minipage}
    }
    \qquad
    \subfloat[Qualidade para a técnica \textit{a priori} com particionamento por \textit{quadtree} para o Cilindro.]
    {\label{fig:quadtree_priori_cilindro_qualidade}
     \begin{minipage}[c]{0.7\textwidth}{\includegraphics[width=\textwidth]{fig/imagens_res_daniel/quadtree_qualidade_cilindro.png}}\end{minipage}
    }
    
    \subfloat[Qualidade para a técnica \textit{a posteriori} com particionamento por \textit{quadtree} para o Cilindro.]
    {\label{fig:quadtree_posteriori_cilindro_qualidade}
     \begin{minipage}[c]{0.7\textwidth}{\includegraphics[width=\textwidth]{fig/imagens_res_markos/posteriori_qualidade_cilindro.png}}\end{minipage}
    }
    \caption{Qualidade para o Cilindro nas três abordagens.}
    \label{fig:qualidades_cilindro}
    \end{figure}           

    
    \begin{figure}[!ht]
    \centering
    \subfloat[Qualidade para a técnica \textit{a priori} com particionamento por BSP para a Chave.]
    {\label{fig:qualidade_chave}
     \begin{minipage}[c]{0.7\textwidth}{\includegraphics[width=\textwidth]{fig/imagens_resultados/qualidade_chave.png}}\end{minipage}
    }
    \qquad
    \subfloat[Qualidade para a técnica \textit{a priori} com particionamento por \textit{quadtree} para a Chave.]
    {\label{fig:quadtree_priori_chave_qualidade}
     \begin{minipage}[c]{0.7\textwidth}{\includegraphics[width=\textwidth]{fig/imagens_res_daniel/quadtree_qualidade_chave.png}}\end{minipage}
    }    
    
    \subfloat[Qualidade para a técnica \textit{a posteriori} com particionamento por \textit{quadtree} para a Chave.]
    {\label{fig:quadtree_posteriori_chave_qualidade}
     \begin{minipage}[c]{0.7\textwidth}{\includegraphics[width=\textwidth]{fig/imagens_res_markos/posteriori_qualidade_chave.png}}\end{minipage}
    }
    \caption{Qualidade para a Chave nas três abordagens.}
    \label{fig:qualidades_chave}
    \end{figure}    
    

    \begin{figure}[!ht]
    \centering
    \subfloat[Qualidade para a técnica \textit{a priori} com particionamento por BSP para a Placa.]
    {\label{fig:qualidade_plate3}
     \begin{minipage}[c]{0.7\textwidth}{\includegraphics[width=\textwidth]{fig/imagens_resultados/qualidade_plate3.png}}\end{minipage}
    }
    \qquad
    \subfloat[Qualidade para a técnica \textit{a priori} com particionamento por \textit{quadtree} para a Placa.]
    {\label{fig:quadtree_priori_plate3_qualidade}
     \begin{minipage}[c]{0.7\textwidth}{\includegraphics[width=\textwidth]{fig/imagens_res_daniel/quadtree_qualidade_plate3.png}}\end{minipage}
    }    

    \subfloat[Qualidade para a técnica \textit{a posteriori} com particionamento por \textit{quadtree} para a Placa.]
    {\label{fig:quadtree_posteriori_plate3_qualidade}
     \begin{minipage}[c]{0.7\textwidth}{\includegraphics[width=\textwidth]{fig/imagens_res_markos/posteriori_qualidade_plate3.png}}\end{minipage}
    }    
    \caption{Qualidade para a Placa nas três abordagens.}
    \label{fig:qualidades_plate3}
    \end{figure}

    
    \FloatBarrier   % FORÇA TUDO SER EXIBIDO ATÉ AQUI

    
Os gráficos de diferença de qualidade ajudam a comparar as malhas geradas em paralelo com as sequenciais. Nesses gráficos, barras acima de zero indicam que mais elementos naquela faixa de valor da métrica de qualidade foram gerados na versão paralela do que na sequencial; barras abaixo de zero indicam que existem mais elementos gerados sequencialmente naquela determinada faixa de valor do que na versão paralela. Algo interessante de se observar é que à medida que mais processos participam da geração da malha, mais essa diferença aumenta. Isso ocorre porque quando se adiciona um novo processo na geração da malha, se adiciona também um novo subdomínio para esse processo. Quanto mais subdivisões forem feitas, mais a malha final vai divergir da malha sequencial.    

    \begin{figure}[!ht]
    \centering
    \subfloat[Diferença de qualidade para a técnica \textit{a priori} com particionamento por \textit{quadtree} para o Cilindro.]
    {\label{fig:quadtree_priori_cilindro_dif_qualidade}
     \begin{minipage}[c]{0.7\textwidth}{\includegraphics[width=\textwidth]{fig/imagens_res_daniel/quadtree_qualidade_dif_cilindro.png}}\end{minipage}
    }
    \qquad
    \subfloat[Diferença de qualidade para a técnica \textit{a posteriori} com particionamento por \textit{quadtree} para o Cilindro.]
    {\label{fig:quadtree_posteriori_cilindro_dif_qualidade}
     \begin{minipage}[c]{0.7\textwidth}{\includegraphics[width=\textwidth]{fig/imagens_res_markos/posteriori_qualidade_dif_cilindro.png}}\end{minipage}
    }
    \caption{Diferença de qualidade para as técnica \textit{a priori} e \textit{posteriori}, utilizando \textit{quadtree} para particionamento.}
    \label{fig:quadtree_comp_dif_qualidade}
    \end{figure}    

     \begin{figure}[!ht]
    \ContinuedFloat
     \centering            
    \subfloat[Diferença de qualidade para a técnica \textit{a priori} com particionamento por \textit{quadtree} para a Chave.]
    {\label{fig:quadtree_priori_chave_dif_qualidade}
     \begin{minipage}[c]{0.7\textwidth}{\includegraphics[width=\textwidth]{fig/imagens_res_daniel/quadtree_qualidade_dif_chave.png}}\end{minipage}
    }    
    \qquad
    \subfloat[Diferença de qualidade para a técnica \textit{a posteriori} com particionamento por \textit{quadtree} para a Chave.]
    {\label{fig:quadtree_posteriori_chave_dif_qualidade}
     \begin{minipage}[c]{0.7\textwidth}{\includegraphics[width=\textwidth]{fig/imagens_res_markos/posteriori_qualidade_dif_chave.png}}\end{minipage}
    }
    \caption{Diferença de qualidade para as técnica \textit{a priori} e \textit{posteriori}, utilizando \textit{quadtree} para particionamento (continuação).}
    \end{figure}    

     \begin{figure}[!ht]
    \ContinuedFloat
     \centering          
    \subfloat[Diferença de qualidade para a técnica \textit{a priori} com particionamento por \textit{quadtree} para a Placa.]
    {\label{fig:quadtree_priori_plate3_dif_qualidade}
     \begin{minipage}[c]{0.7\textwidth}{\includegraphics[width=\textwidth]{fig/imagens_res_daniel/quadtree_qualidade_dif_plate3.png}}\end{minipage}
    }    
    \qquad
    \subfloat[Diferença de qualidade para a técnica \textit{a posteriori} com particionamento por \textit{quadtree} para a Placa.]
    {\label{fig:quadtree_posteriori_plate3_dif_qualidade}
     \begin{minipage}[c]{0.7\textwidth}{\includegraphics[width=\textwidth]{fig/imagens_res_markos/posteriori_qualidade_dif_plate3.png}}\end{minipage}
    }    
    \caption{Diferença de qualidade para as técnica \textit{a priori} e \textit{posteriori}, utilizando \textit{quadtree} para particionamento (continuação).}
    %\label{fig:quadtree_comp_dif_qualidade}
    \end{figure}    

    
    \FloatBarrier   % FORÇA TUDO SER EXIBIDO ATÉ AQUI
    
    
Como pode ser visto nas figuras desta seção, em todos os casos, as malhas geradas apresentam boa qualidade. Somente uma pequena porcentagem de elementos apresentam qualidade muito diferente de 1,0. Outro fato que se observa é que à medida que se aumenta o número de processadores a qualidade dos elementos diminui, e isso ocorre por conta da quantidade de subdomínios que aumenta à medida que novos processadores são usados. A utilização do particionamento por BSP melhora a qualidade, mas, mesmo assim, não apresenta uma qualidade superior à da técnica \textit{a posteriori}.

No entanto, a técnica paralela descrita neste trabalho gera uma malha de qualidade aproximadamente igual à da malha gerada sequencialmente. Note também que um número maior de subdomínios criados geralmente leva a diminuição da qualidade da malha.

     \begin{figure}[!ht]
    \centering
    \subfloat[Diferença de qualidade para a técnica \textit{a priori} com particionamento por BSP para o Cilindro.]
    {\label{fig:dif_qualidade_cilindro}
     \begin{minipage}[c]{0.7\textwidth}{\includegraphics[width=\textwidth]{fig/imagens_resultados/dif_qualidade_cilindro.png}}\end{minipage}
    }
    \qquad
    \subfloat[Diferença de qualidade para a técnica \textit{a priori} com particionamento por BSP para a Chave.]
    {\label{fig:dif_qualidade_chave}
     \begin{minipage}[c]{0.7\textwidth}{\includegraphics[width=\textwidth]{fig/imagens_resultados/dif_qualidade_chave.png}}\end{minipage}
    }
    \caption{Diferença de qualidade dos elementos em porcentagem para as técnica \textit{a priori} utilizando BSP para particionamento.}    
    \label{fig:bsp_dif_qualidades}
    \end{figure}   


     \begin{figure}[!ht]
    \ContinuedFloat
     \centering             
    \subfloat[Diferença de qualidade para a técnica \textit{a priori} com particionamento por BSP para a Placa.]
    {\label{fig:dif_qualidade_plate3}
     \begin{minipage}[c]{0.7\textwidth}{\includegraphics[width=\textwidth]{fig/imagens_resultados/dif_qualidade_plate3.png}}\end{minipage}
    }
    \caption{Diferença de qualidade dos elementos em porcentagem para as técnica \textit{a priori} utilizando BSP para particionamento (continuação).}    
    %\label{fig:bsp_dif_qualidades}
    \end{figure}   


\section{Tempo de execução e \textit{speed-up}}

Os gráficos da Figura \ref{fig:speed_up_dif} mostram o \textit{speed-up} atingido pela implementação das duas técnicas mudando somente a estrutura de particionamento para a técnica \textit{a priori}. Como dito anteriormente na Seção \ref{Metricas de desempenho}, o \textit{speed-up} indica quantas vezes a implementação foi mais rápida quando uma determinada quantidade de processos foi utilizada. Idealmente, uma implementação paralela teria um \textit{speed-up} linear, significando que $n$ processos a tornam $n$ vezes mais rápida. Na prática, isso é difícil de ser obtido, por causa das inevitáveis porções sequenciais presentes no algoritmo paralelo, além do tempo de comunicação entre os processos, que não existe no caso sequencial.

    \begin{figure}[!ht]
    \centering
    \subfloat[\textit{Speed-up} para as três abordagens no modelo Cilindro.]
    {\label{fig:speed_up_dif_cilindro}
     \begin{minipage}[c]{0.7\textwidth}{\includegraphics[width=\textwidth]{fig/imagens_resultados/speed_up_geral_cilindro.png}}\end{minipage}
    }
    \qquad
    \subfloat[\textit{Speed-up} para as três abordagens no modelo Chave.]
    {\label{fig:speed_up_dif_chave}
     \begin{minipage}[c]{0.7\textwidth}{\includegraphics[width=\textwidth]{fig/imagens_resultados/speed_up_geral_chave.png}}\end{minipage}
    }
    \caption{\textit{Speed-up} para as três abordagens.}    
    \label{fig:speed_up_dif}
    \end{figure}    


     \begin{figure}[!ht]
    \ContinuedFloat
     \centering           
    \subfloat[\textit{Speed-up} para as três abordagens no modelo Placa.]
    {\label{fig:speed_up_dif_plate3}
     \begin{minipage}[c]{0.6\textwidth}{\includegraphics[width=\textwidth]{fig/imagens_resultados/speed_up_geral_plate3.png}}\end{minipage}
    }
    \caption{\textit{Speed-up} para as três abordagens (continuação).}    
    %\label{fig:speed_up_dif}
    \end{figure}   

Do lado esquerdo dos gráficos é mostrado o valor do \textit{speed-up}. No eixo X é mostrada a variação na quantidade de processos utilizados na geração da malha. Pode-se notar que o \textit{speed-up} da técnica descrita neste trabalho foi bem superior ao da técnica \textit{a posteriori}. A utilização da BSP para particionamento melhorou o \textit{speed-up} quando comparado com as outras duas abordagens.

Na Figura \ref{fig:bsp_tempo_exe_dif}, é mostrado o tempo de execução atingido pela implementação das duas técnicas mudando somente a estrutura de particionamento para a técnica \textit{a priori}. Do lado esquerdo dos gráficos é mostrado o tempo de execução em segundos. A abordagem \textit{a priori} com decomposição baseada na BSP obteve os melhores resultados em todos os exemplos.


    \begin{figure}[!ht]
    \centering
    \subfloat[Tempo de execução para as três abordagens no modelo Cilindro.]
    {\label{fig:bsp_tempo_exe_dif_cilindro}
     \begin{minipage}[c]{0.6\textwidth}{\includegraphics[width=\textwidth]{fig/imagens_resultados/velocidade_geral_cilindro.png}}\end{minipage}
    }
    \caption{Tempo de execução para as três abordagens.}    
    \label{fig:bsp_tempo_exe_dif}
    \end{figure}    


     \begin{figure}[!ht]
    \ContinuedFloat
     \centering          
    \subfloat[Tempo de execução para as três abordagens no modelo Chave.]
    {\label{fig:bsp_tempo_exe_dif_chave}
     \begin{minipage}[c]{0.7\textwidth}{\includegraphics[width=\textwidth]{fig/imagens_resultados/velocidade_geral_chave.png}}\end{minipage}
    }
    
    \subfloat[Tempo de execução para as três abordagens no modelo Placa.]
    {\label{fig:bsp_tempo_exe_dif_plate3}
     \begin{minipage}[c]{0.7\textwidth}{\includegraphics[width=\textwidth]{fig/imagens_resultados/velocidade_geral_plate3.png}}\end{minipage}
    }
    \caption{Tempo de execução para as três abordagens (continuação).}    
    %\label{fig:bsp_tempo_exe_dif}
    \end{figure}   

A técnica \textit{a priori} é mais rápida que \textit{a posteriori} além de apresentar uma escalabilidade melhor. O uso da BSP melhora os resultados e isso se deve a uma melhor adaptação desta estrutura de dados ao domínio dado como entrada. Os próximos resultados que serão exibidos não apresentam mais a técnica \textit{a posteriori} pois a técnica \textit{a priori} mostrou-se mais rápida em todos os modelos. Então, a partir de agora, são comparadas somente as técnicas \textit{a priori} com particionamento feito por BSP e por \textit{quadtree}.


    \FloatBarrier   % FORÇA TUDO SER EXIBIDO ATÉ AQUI

    
\section{Balanceamento de Carga} 
 
Nesta seção, é mostrado o balanceamento da carga, levando em conta o número de elementos gerados em cada subdomínio, que é considerado neste trabalho como carga. Os gráficos das Figuras \ref{fig:balanceamento_quadtree_cilindro}, \ref{fig:balanceamento_quadtree_chave} e \ref{fig:balanceamento_quadtree_plate3} mostram que, para os três exemplos, a técnica, que utiliza particionamento por \textit{quadtree}, tem uma carga bem distribuída entre os processos. A esquerda dos gráficos fica a quantidade de elementos gerados, no eixo X é exibida a quantidade de processos e nas barras de valores ficam os subdomínios representados por diferentes cores. Utilizando um particionamento com \textit{quadtree}, a quantidade de subdomínios criados pode ser maior que a quantidade de processos disponíveis, e por isso aparecem processos aos quais estão atribuídos dois ou mais subdomínios. 

Nas figuras \ref{fig:balanceamento_bsp_cilindro}, \ref{fig:balanceamento_bsp_chave} e \ref{fig:balanceamento_bsp_plate3}, estão exibidos os gráficos para o balanceamento utilizando particionamento por BSP. Além da quantidade de elementos, é exibido o tempo de execução em segundos, representados pelas barras laranja e azul respectivamente. Pode-se observar que o tempo de execução é diretamente proporcional à quantidade de elementos gerados e que tanto o tempo de execução como o número de elementos se mantêm balanceados nos gráficos. Até no exemplo da Chave, que possui uma geometria bastante complexa, as barras de tempo de execução e a quantidade de elementos se mantiveram niveladas.
 
 
     \begin{figure}[!ht]
    \centering
    \subfloat[Balanceamento pelo número de elementos do exemplo Cilindro com 2 processos com particionamento por \textit{quadtree}.]
    {\label{fig:balanceamento_quadtree_cilindro2}
     \begin{minipage}[c]{0.45\textwidth}{\includegraphics[width=\textwidth]{fig/imagens_res_daniel/balanceamento_quadtree_2_cilindro.png}}\end{minipage}
    }
    \qquad
    \subfloat[Balanceamento pelo número de elementos do exemplo Cilindro com 4 processos com particionamento por \textit{quadtree}.]
    {\label{fig:balanceamento_quadtree_cilindro4}
     \begin{minipage}[c]{0.45\textwidth}{\includegraphics[width=\textwidth]{fig/imagens_res_daniel/balanceamento_quadtree_4_cilindro.png}}\end{minipage}
    }
    \caption{Balanceamento pelo número de elementos do exemplo Cilindro para 2, 4, 6 e 8 processos com particionamento por \textit{quadtree}.}
    \label{fig:balanceamento_quadtree_cilindro}
    \end{figure}    

     \begin{figure}[!ht]
    \ContinuedFloat
     \centering        
    \subfloat[Balanceamento pelo número de elementos do exemplo Cilindro com 6 processos com particionamento por \textit{quadtree}.]
    {\label{fig:balanceamento_quadtree_cilindro6}
     \begin{minipage}[c]{0.45\textwidth}{\includegraphics[width=\textwidth]{fig/imagens_res_daniel/balanceamento_quadtree_6_cilindro.png}}\end{minipage}
    }
    \qquad
    \subfloat[Balanceamento pelo número de elementos do exemplo Cilindro com 8 processos com particionamento por \textit{quadtree}.]
    {\label{fig:balanceamento_quadtree_cilindro8}
     \begin{minipage}[c]{0.45\textwidth}{\includegraphics[width=\textwidth]{fig/imagens_res_daniel/balanceamento_quadtree_8_cilindro.png}}\end{minipage}
    }
    \caption{Balanceamento pelo número de elementos do exemplo Cilindro para 2, 4, 6 e 8 processos com particionamento por \textit{quadtree} (continuação).}
    \end{figure}
 
 
 
    \begin{figure}[!ht]
    \centering
    \subfloat[Balanceamento pelo número de elementos do exemplo Cilindro com 2 processos com particionamento por BSP.]
    {\label{fig:balanceamento_bsp_cilindro2}
     \begin{minipage}[c]{0.45\textwidth}{\includegraphics[width=\textwidth]{fig/imagens_resultados/balanceamento_2_cilindro.png}}\end{minipage}
    }
    \qquad
    \subfloat[Balanceamento pelo número de elementos do exemplo Cilindro com 4 processos com particionamento por BSP.]
    {\label{fig:balanceamento_bsp_cilindro4}
     \begin{minipage}[c]{0.45\textwidth}{\includegraphics[width=\textwidth]{fig/imagens_resultados/balanceamento_4_cilindro.png}}\end{minipage}
    }
    
    \subfloat[Balanceamento pelo número de elementos do exemplo Cilindro com 6 processos com particionamento por BSP.]
    {\label{fig:balanceamento_bsp_cilindro6}
     \begin{minipage}[c]{0.45\textwidth}{\includegraphics[width=\textwidth]{fig/imagens_resultados/balanceamento_6_cilindro.png}}\end{minipage}
    }
    \qquad
    \subfloat[Balanceamento pelo número de elementos do exemplo Cilindro com 8 processos com particionamento por BSP.]
    {\label{fig:balanceamento_bsp_cilindro8}
     \begin{minipage}[c]{0.45\textwidth}{\includegraphics[width=\textwidth]{fig/imagens_resultados/balanceamento_8_cilindro.png}}\end{minipage}
    }
    \caption{Balanceamento pelo número de elementos do exemplo Cilindro para 2, 4, 6 e 8 processos com particionamento por BSP.}
    \label{fig:balanceamento_bsp_cilindro}
    \end{figure}

        
    
     \begin{figure}[!ht]
    \centering
    \subfloat[Balanceamento pelo número de elementos do exemplo Chave com 2 processos com particionamento por \textit{quadtree}.]
    {\label{fig:balanceamento_quadtree_chave2}
     \begin{minipage}[c]{0.45\textwidth}{\includegraphics[width=\textwidth]{fig/imagens_res_daniel/balanceamento_quadtree_2_chave.png}}\end{minipage}
    }
    \qquad
    \subfloat[Balanceamento pelo número de elementos do exemplo Chave com 4 processos com particionamento por \textit{quadtree}.]
    {\label{fig:balanceamento_quadtree_chave4}
     \begin{minipage}[c]{0.45\textwidth}{\includegraphics[width=\textwidth]{fig/imagens_res_daniel/balanceamento_quadtree_4_chave.png}}\end{minipage}
    }

    \subfloat[Balanceamento pelo número de elementos do exemplo Chave com 6 processos com particionamento por \textit{quadtree}.]
    {\label{fig:balanceamento_quadtree_chave6}
     \begin{minipage}[c]{0.45\textwidth}{\includegraphics[width=\textwidth]{fig/imagens_res_daniel/balanceamento_quadtree_6_chave.png}}\end{minipage}
    }
    \qquad
    \subfloat[Balanceamento pelo número de elementos do exemplo Chave com 8 processos com particionamento por \textit{quadtree}.]
    {\label{fig:balanceamento_quadtree_chave8}
     \begin{minipage}[c]{0.45\textwidth}{\includegraphics[width=\textwidth]{fig/imagens_res_daniel/balanceamento_quadtree_8_chave.png}}\end{minipage}
    }
    \caption{Balanceamento pelo número de elementos do exemplo Chave para 2, 4, 6 e 8 processos com particionamento por \textit{quadtree}.}
    \label{fig:balanceamento_quadtree_chave}
    \end{figure}
 
 
 
    \begin{figure}[!ht]
    \centering
    \subfloat[Balanceamento pelo número de elementos do exemplo Chave com 2 processos com particionamento por BSP.]
    {\label{fig:balanceamento_bsp_chave2}
     \begin{minipage}[c]{0.45\textwidth}{\includegraphics[width=\textwidth]{fig/imagens_resultados/balanceamento_2_chave.png}}\end{minipage}
    }
    \qquad
    \subfloat[Balanceamento pelo número de elementos do exemplo Chave com 4 processos com particionamento por BSP.]
    {\label{fig:balanceamento_bsp_chave4}
     \begin{minipage}[c]{0.45\textwidth}{\includegraphics[width=\textwidth]{fig/imagens_resultados/balanceamento_4_chave.png}}\end{minipage}
    }
    \caption{Balanceamento pelo número de elementos do exemplo Chave para 2, 4, 6 e 8 processos com particionamento por BSP.}
    \label{fig:balanceamento_bsp_chave}
    \end{figure}    

     \begin{figure}[!ht]
    \ContinuedFloat
     \centering            
    \subfloat[Balanceamento pelo número de elementos do exemplo Chave com 6 processos com particionamento por BSP.]
    {\label{fig:balanceamento_bsp_chave6}
     \begin{minipage}[c]{0.45\textwidth}{\includegraphics[width=\textwidth]{fig/imagens_resultados/balanceamento_6_chave.png}}\end{minipage}
    }
    \qquad
    \subfloat[Balanceamento pelo número de elementos do exemplo Chave com 8 processos com particionamento por BSP.]
    {\label{fig:balanceamento_bsp_chave8}
     \begin{minipage}[c]{0.45\textwidth}{\includegraphics[width=\textwidth]{fig/imagens_resultados/balanceamento_8_chave.png}}\end{minipage}
    }
    \caption{Balanceamento pelo número de elementos do exemplo Chave para 2, 4, 6 e 8 processos com particionamento por BSP (continuação).}
    \end{figure}    
    
    
    
     \begin{figure}[!ht]
    \centering
    \subfloat[Balanceamento pelo número de elementos do exemplo Placa com 2 processos com particionamento por \textit{quadtree}.]
    {\label{fig:balanceamento_quadtree_plate2}
     \begin{minipage}[c]{0.45\textwidth}{\includegraphics[width=\textwidth]{fig/imagens_res_daniel/balanceamento_quadtree_2_plate3.png}}\end{minipage}
    }
    \qquad
    \subfloat[Balanceamento pelo número de elementos do exemplo Placa com 4 processos com particionamento por \textit{quadtree}.]
    {\label{fig:balanceamento_quadtree_plate4}
     \begin{minipage}[c]{0.45\textwidth}{\includegraphics[width=\textwidth]{fig/imagens_res_daniel/balanceamento_quadtree_4_plate3.png}}\end{minipage}
    }
    
    \subfloat[Balanceamento pelo número de elementos do exemplo Placa com 6 processos com particionamento por \textit{quadtree}.]
    {\label{fig:balanceamento_quadtree_plate6}
     \begin{minipage}[c]{0.45\textwidth}{\includegraphics[width=\textwidth]{fig/imagens_res_daniel/balanceamento_quadtree_6_plate3.png}}\end{minipage}
    }
    \qquad
    \subfloat[Balanceamento pelo número de elementos do exemplo Placa com 8 processos com particionamento por \textit{quadtree}.]
    {\label{fig:balanceamento_quadtree_plate8}
     \begin{minipage}[c]{0.45\textwidth}{\includegraphics[width=\textwidth]{fig/imagens_res_daniel/balanceamento_quadtree_8_plate3.png}}\end{minipage}
    }
    \caption{Balanceamento pelo número de elementos do exemplo Placa para 2, 4, 6 e 8 processos com particionamento por \textit{quadtree}.}
    \label{fig:balanceamento_quadtree_plate3}
    \end{figure}

    
    \FloatBarrier   % FORÇA TUDO SER EXIBIDO ATÉ AQUI
 
 
    \begin{figure}[!ht]
    \centering
    \subfloat[Balanceamento pelo número de elementos do exemplo Placa com 2 processos com particionamento por BSP.]
    {\label{fig:balanceamento_bsp_plate2}
     \begin{minipage}[c]{0.45\textwidth}{\includegraphics[width=\textwidth]{fig/imagens_resultados/balanceamento_2_plate3.png}}\end{minipage}
    }
    \qquad
    \subfloat[Balanceamento pelo número de elementos do exemplo Placa com 4 processos com particionamento por BSP.]
    {\label{fig:balanceamento_bsp_plate4}
     \begin{minipage}[c]{0.45\textwidth}{\includegraphics[width=\textwidth]{fig/imagens_resultados/balanceamento_4_plate3.png}}\end{minipage}
    }

    \subfloat[Balanceamento pelo número de elementos do exemplo Placa com 6 processos com particionamento por BSP.]
    {\label{fig:balanceamento_bsp_plate6}
     \begin{minipage}[c]{0.45\textwidth}{\includegraphics[width=\textwidth]{fig/imagens_resultados/balanceamento_6_plate3.png}}\end{minipage}
    }
    \qquad
    \subfloat[Balanceamento pelo número de elementos do exemplo Placa com 8 processos com particionamento por BSP.]
    {\label{fig:balanceamento_bsp_plate8}
     \begin{minipage}[c]{0.45\textwidth}{\includegraphics[width=\textwidth]{fig/imagens_resultados/balanceamento_8_plate3.png}}\end{minipage}
    }
    \caption{Balanceamento pelo número de elementos do exemplo Placa para 2, 4, 6 e 8 processos com particionamento por BSP.}
    \label{fig:balanceamento_bsp_plate3}
    \end{figure}    
    

A grande vantagem da BSP se encontra na criação dos subdomínios, onde a melhor posição para se gerar uma fronteira é encontrada. Isso mantém um balanceamento muito bom e evita a criação excessiva de subdomínios, reduzindo assim tempos de comunicação. Com o uso da \textit{quadtree} nem sempre um bom balanceamento é possível como mostrado da figura \ref{fig:balanceamento_quadtree_cilindro8}, por exemplo. Um estratégia que pode melhorar o particionamento é subdividir o domínio até que a diferença de carga nos processos seja menor que um dado limite, pois isso melhora o balanceamento mas pode criar subdomínios em excesso e aumentar a comunicação entre processos.


\section{Estimativa de Carga} 

Com o objetivo de provar que a estimativa de carga descrita na Seção~\ref{sec:Estimativa_carga} é acurada, o tempo de execução levado para gerar a malha em cada subdomínio foi calculado e comparado com a carga estimada para aquele subdomínio. A Figura \ref{fig:geral_estimativa} compara o tempo de execução de cada passo do procedimento de avanço de fronteira e o tempo de execução estimado para alguns subdomínios. É exibido somente a estimativa para alguns processos pois com essa quantidade já é possível se ter uma ideia do comportamento da técnica. Representar todos os subdomínios não caberia no gráfico, além de não ser necessário para esta comparação.

     \begin{figure}[!ht]
    \centering
    \subfloat[Estimativa de tempo de execução para o Cilindro com particionamento feito por \textit{quadtree}.]
    {\label{fig:geral_quadtree_cilindro}
     \begin{minipage}[c]{1.0\textwidth}{\includegraphics[width=\textwidth]{fig/imagens_res_daniel/quadtree_tempo_cilindro.png}}\end{minipage}
    }
    \qquad
    \subfloat[Estimativa de tempo de execução para o Cilindro com particionamento feito por BSP.]
    {\label{fig:geral_bsp_cilindro}
      \begin{minipage}[c]{1.0\textwidth}{\includegraphics[width=\textwidth]{fig/imagens_resultados/tempo_cilindro.png}}\end{minipage}     
    }

    \subfloat[Estimativa de tempo de execução para a Chave com particionamento feito por \textit{quadtree}.]
    {\label{fig:geral_quadtree_chave}
     \begin{minipage}[c]{1.0\textwidth}{\includegraphics[width=\textwidth]{fig/imagens_res_daniel/quadtree_tempo_chave.png}}\end{minipage}
    }
    \caption{Estimativas de tempo de execução dos modelos com particionamento feito por \textit{quadtree} e BSP.}
    \label{fig:geral_estimativa}
    \end{figure} 
    
     \begin{figure}[!ht]
    \ContinuedFloat
     \centering        
    \subfloat[Estimativa de tempo de execução para a Chave com particionamento feito por BSP.]
    {\label{fig:geral_bsp_chave}
     \begin{minipage}[c]{1.0\textwidth}{\includegraphics[width=\textwidth]{fig/imagens_resultados/tempo_chave.png}}\end{minipage}     
    }
    
    \subfloat[Estimativa de tempo de execução para a Placa com particionamento feito por \textit{quadtree}.]
    {\label{fig:geral_quadtree_plate3}
     \begin{minipage}[c]{1.0\textwidth}{\includegraphics[width=\textwidth]{fig/imagens_res_daniel/quadtree_tempo_plate3.png}}\end{minipage}
    }
    \qquad
    \subfloat[Estimativa de tempo de execução para a Placa com particionamento feito por BSP.]
    {\label{fig:geral_bsp_plate3}
     \begin{minipage}[c]{1.0\textwidth}{\includegraphics[width=\textwidth]{fig/imagens_resultados/tempo_plate3.png}}\end{minipage}
    }    
    \caption{Estimativas de tempo de execução dos modelos com particionamento feito por \textit{quadtree} e BSP (continuação).}
    \end{figure} 
 
 
 \FloatBarrier
Os passos de avanço de fronteira e de melhoria da malha pertencem ao procedimento de geração de malha empregado, e o passo de classificação das células que foi descrito na Seção \ref{sec:Parallel_mesh_generation_Mesh_generation_by_a_slave_process} está incluso no passo criação e destruição da árvore de busca. O passo de \textit{Overhead} contabiliza o tempo extra gasto fazendo trabalho improdutivo como busca em listas.

Quando a \textit{quadtree} é utilizada na partição de domínio, a quantidade de subdomínios gerados é muito grande. Isso faz com que a carga associada a  alguns subdomínios seja muito baixa (vide Figuras \ref{fig:geral_quadtree_chave} e \ref{fig:geral_quadtree_plate3}). No entanto, quando BSP é usada na partição de domínio, a quantidade de tarefas geradas é igual ao número de processos.

     \begin{figure}[!ht]
    \centering
    \subfloat[Estimativa de elementos e vértices para o Cilindro com particionamento feito por \textit{quadtree}.]
    {\label{fig:estimativa_quadtree_cilindro}
     \begin{minipage}[c]{0.85\textwidth}{\includegraphics[width=\textwidth]{fig/imagens_res_daniel/quadtree_estimativa_cilindro.png}}\end{minipage}
    }

    \subfloat[Estimativa de elementos e vértices para o Cilindro com particionamento feito por BSP.]
    {\label{fig:estimativa_bsp_cilindro}
      \begin{minipage}[c]{0.85\textwidth}{\includegraphics[width=\textwidth]{fig/imagens_resultados/estimativa_cilindro.png}}\end{minipage}     
    }
    \caption{Estimativas de elementos e vértices dos modelos com particionamento feito por \textit{quadtree} e BSP.}
    \label{fig:estimativa_vertices_elementos}
    \end{figure} 
    
     \begin{figure}[!ht]
    \ContinuedFloat
     \centering        
    \subfloat[Estimativa de elementos e vértices para o Chave com particionamento feito por \textit{quadtree}.]
    {\label{fig:estimativa_quadtree_chave}
     \begin{minipage}[c]{0.85\textwidth}{\includegraphics[width=\textwidth]{fig/imagens_res_daniel/quadtree_estimativa_chave.png}}\end{minipage}
    }

    \subfloat[Estimativa de elementos e vértices para a Chave com particionamento feito por BSP.]
    {\label{fig:estimativa_bsp_chave}
     \begin{minipage}[c]{0.85\textwidth}{\includegraphics[width=\textwidth]{fig/imagens_resultados/estimativa_chave.png}}\end{minipage}     
    }
    
    \subfloat[Estimativa de elementos e vértices para a Placa com particionamento feito por \textit{quadtree}.]
    {\label{fig:estimativa_quadtree_palte3}
     \begin{minipage}[c]{0.85\textwidth}{\includegraphics[width=\textwidth]{fig/imagens_res_daniel/quadtree_estimativa_plate3.png}}\end{minipage}
    }
    \caption{Estimativas de elementos e vértices dos modelos com particionamento feito por \textit{quadtree} e BSP (continuação).}
    \end{figure} 
 
\FloatBarrier 

     \begin{figure}[!ht]
    \ContinuedFloat
     \centering      
    \subfloat[Estimativa de elementos e vértices para a Placa com particionamento feito por BSP.]
    {\label{fig:estimativa_bsp_plate3}
     \begin{minipage}[c]{0.85\textwidth}{\includegraphics[width=\textwidth]{fig/imagens_resultados/estimativa_plate3.png}}\end{minipage}
    }    
    \caption{Estimativas de elementos e vértices dos modelos com particionamento feito por \textit{quadtree} e BSP (continuação).}
    \end{figure}     
    
As linhas na Figura \ref{fig:geral_estimativa} representam o tempo de execução estimado, que foi calculado como a carga multiplicada pelo fator $\bar t/\bar l$, onde $\bar t$ é o tempo médio de execução e $\bar l$ é a carga média estimada para os subdomínios. Já que somente a proporção entre as cargas é necessária para o balanceamento de carga, este fator fixo pode ser aplicado para propósito de avaliação. A Figura \ref{fig:estimativa_vertices_elementos} mostra as mesmas comparações, mas considerando o número de elementos e o número de vértices em vez do tempo de execução. As linhas mostram a estimativa, enquanto as barras mostram a quantidade real gerada; como pode ser visto, a estimativa é precisa.

 

Vale lembrar que a  estimativa da carga de um subdomínio é um valor que não tem um significado concreto mas que, quando comparado à estimativa de um outro subdomínio, ganha significado. Se a estimativa de carga para um subdomínio for 100 não necessariamente quer dizer que 100 elementos serão gerados mas, quando comparado à uma carga duas vezes maior de outro subdomínio, o valor de 200 quer dizer que este subdomínio gerará o dobro de elementos do outro subdomínio.

     \begin{figure}[!ht]
    \centering
    \subfloat[Erro na estimativa de elementos e vértices para o Cilindro com particionamento feito por \textit{quadtree}.]
    {\label{fig:erro_estimativa_quadtree_cilindro}
     \begin{minipage}[c]{1.0\textwidth}{\includegraphics[width=\textwidth]{fig/imagens_res_daniel/quadtree_estimativa_erro_cilindro.png}}\end{minipage}
    }
    \qquad
    \subfloat[Erro na estimativa de elementos e vértices para o Cilindro com particionamento feito por \textit{quadtree}.]
    {\label{fig:erro_estimativa_bsp_cilindro}
      \begin{minipage}[c]{1.0\textwidth}{\includegraphics[width=\textwidth]{fig/imagens_resultados/estimativa_erro_cilindro.png}}\end{minipage}     
    }
    \caption{Erro na estimativa de elementos e vértices dos modelos com particionamento feito por \textit{quadtree} e BSP.}
    \label{fig:erro_estimativa}
    \end{figure} 
    
     \begin{figure}[!ht]
    \ContinuedFloat
     \centering            
    \subfloat[Erro na estimativa de elementos e vértices para a Chave com particionamento feito por \textit{quadtree}.]
    {\label{fig:erro_estimativa_quadtree_chave}
     \begin{minipage}[c]{1.0\textwidth}{\includegraphics[width=\textwidth]{fig/imagens_res_daniel/quadtree_estimativa_erro_chave.png}}\end{minipage}
    }
    \qquad
    \subfloat[Erro na estimativa de elementos e vértices para a Chave com particionamento feito por \textit{quadtree}.]
    {\label{fig:erro_estimativa_bsp_chave}
     \begin{minipage}[c]{1.0\textwidth}{\includegraphics[width=\textwidth]{fig/imagens_resultados/estimativa_erro_chave.png}}\end{minipage}     
    }
    \caption{Erro na estimativa de elementos e vértices dos modelos com particionamento feito por \textit{quadtree} e BSP (continuação).}
    \end{figure} 
    
     \begin{figure}[!ht]
    \ContinuedFloat
     \centering               
    \subfloat[Erro na estimativa de elementos e vértices para a Placa com particionamento feito por \textit{quadtree}.]
    {\label{fig:erro_estimativa_quadtree_palte3}
     \begin{minipage}[c]{1.0\textwidth}{\includegraphics[width=\textwidth]{fig/imagens_res_daniel/quadtree_estimativa_erro_plate3.png}}\end{minipage}
    }
    \qquad
    \subfloat[Erro na estimativa de elementos e vértices para a Placa com particionamento feito por \textit{quadtree}.]
    {\label{fig:erro_estimativa_bsp_plate3}
     \begin{minipage}[c]{1.0\textwidth}{\includegraphics[width=\textwidth]{fig/imagens_resultados/estimativa_erro_plate3.png}}\end{minipage}
    }    
    \caption{Erro na estimativa de elementos e vértices dos modelos com particionamento feito por \textit{quadtree} e BSP (continuação).}
    \end{figure} 

Os gráficos da Figura \ref{fig:erro_estimativa} mostram o erro na quantidade de elementos gerados. Quando a barra azul do erro no número de elementos estimados está acima de zero significa que foram gerados mais elementos que o estimado, e quando está abaixo de zero significa que foram gerados menos elementos que o esperado. Nos exemplos do Cilindro e Placa (Figuras \ref{fig:erro_estimativa_bsp_cilindro} e \ref{fig:erro_estimativa_bsp_plate3}) com particionamento feito por BSP, o erro médio se manteve bastante baixo; já no caso da Chave o erro é bem maior se comparado com os anteriores e varia em torno de $2\%$. Isso se deve ao fato da geometria da Chave ser bastante recortada. O mesmo fato acontece quanto o modelo é particionado com uma \textit{quadtree}, mas utilizando-se a BSP o erro médio na estimativa é bem menor.

Os resultados evidenciam que são criados subdomínios carga e tempo de execução sempre nivelados. Até mesmo nos casos em que o modelo tem uma geometria complexa a estimativa se manteve boa, graças à adaptatividade que a BSP possui. Isso não acontece quando uma \textit{quadtree} de particionamento é empregada, como é possível ver nas Figuras \ref{fig:estimativa_vertices_elementos} e \ref{fig:geral_estimativa}.

\FloatBarrier

Os dados exibidos nesta seção mostram que o método empregado, baseado em uma \textit{quadtree} para estimar a carga, produz uma estimativa de boa precisão para o número de elementos e de vértices. Além disso, foram apresentados os resultados de particionamentos feitos por \textit{quadtree} e BSP e suas diferenças. 


\section{Considerações Finais} 

Neste capítulo foram apresentados alguns resultados da técnica proposta. Além disso, foram mostradas comparações da técnica proposta, que usa uma abordagem \textit{a priori}, com uma outra técnica de decomposição \cite{bib:MFreitas13} que é baseada em uma decomposição \textit{a posteriori}.

A técnica proposta neste trabalho consegue gerar uma malha de qualidade, com níveis bem próximos da malha gerada de forma sequencial. Com relação à comparação  entre as duas técnicas (\textit{a priori} e \textit{a posteriori}), é possível constatar que a técnica \textit{a posteriori} possui uma qualidade mais próxima à da malha gerada sequencialmente, tendo uma diferença menor que a técnica descrita neste trabalho. Esse fato já era esperado, pois abordagens contínuas de particionamento \textit{a posteriori} não criam fronteiras limitando a geração da malha naquelas regiões onde foi particionado, fato que ocorre em abordagens contínuas \textit{a priori}. Isso, entretanto, não é um problema sério pois a qualidade da malha não varia muito como foi mostrado e esse aspecto ocorre, em geral, em regiões internas do modelo, onde isso não é crucial na maioria dos casos.

Com relação à questão de velocidade a técnica apresentada neste trabalho apresenta um \textit{speed-up} próximo do linear e é melhor quando comparada com a do trabalho de \cite{bib:MFreitas13}. Além de apresentar os resultados do particionamento feito por \textit{quadtree}, também foram mostrados os resultados usando BSP. Comparando os resultados obtidos pelas duas estruturas, concluiu-se que a BSP é melhor que a \textit{quadtree}, pois a qualidade da malha e a velocidade de geração da malha quando uma BSP é usada no particionamento do domínio são bem melhores. 